The Lightest Language

Memory limit: 32 MB

Alphabet consists of initial letters of English alphabet. A positive integer called a weight is assigned to each letter of the alphabet. A weight of a word built from the letters of the alphabet is the sum of weights of all letters in this word. A language over an alphabet is any finite set of words built from the letters of this alphabet. A weight of a language is the sum of weights of all its words.

We say that the language is prefixless if for each pair of different words , from this language is not a prefix of . We want to find out what is the minimal possible weight of an -element, prefixless language over an alphabet .

Example

Assume that , the weight of the letter — and the weight of the letter — . Then the weight of the word — . . The weight of the language — . The language is not prefixless, since the word is a prefix of . The lightest tree-element, prefixless language over the alphabet (assuming that weights of the letters are as before) is ; its weight is .

Task

Write a program that:

• reads two integers and the weights of letters of an alphabet from the standard input;
• computes the minimal weight of a prefixless, -element language over the alphabet ;
• writes the result to the standard output.

Input

In the first line of the standard input there are two positive integers and separated by a single space, (, ). These are the number of words in a language and the number of letters in an alphabet respectively. The second line contains positive integers separated by single spaces. Each of them is not greater than . The -th number is the weight of the -th letter.

Output

In the first and only line of the standard output there should be written one integer — the weight of the lightest prefixless -element language over the alphabet .

Example

For the input data:

3 2
2 5

the correct result is:

16

Task author: Wojciech Rytter.